





<HTML>

<HEAD>

<LINK rel="stylesheet" href="../exer.css">

</HEAD>

<BODY>

<H1>

Data Structures, Algorithms, & Applications in C++<BR>

Chapter 12, Exercise 21<BR>

<BR>

</H1>



For packed-adjacency lists, assume that 

<code class=code>h</code> and <code class=code>l</code>

are of type <code class=code>int</int> and that each

<code class=code>int</code> is 2 bytes.

The space needed for <code class=code>h</code> is

<em class=var>2(n+1)</em> bytes and that needed for

<code class=code>l</code> is

<em class=var>2e</em> bytes.

The total space required is

<em class=var>2e + 2n + 2</em> bytes.

<br><br>



When the adjacency matrix is represented using one <code class=var>int</code>

for each entry, the space needed is <em class = var>2n<sup>2</sup></em>

bytes.  In this case, the adjacency matrix uses less space provided

<em class=var>e &gt; n<sup>2</sup>-n-1</em>.

<br><br>



If we pack 16 adjacency matrix elements into an

<code class=var>int</code> (see Exercise 12), the space taken by the adjacency

matrix drops to <em class=var>n<sup>2</sup>/8</em> bytes.

Now, the adjacency matrix uses less space provided

<em class=var>e &gt; n<sup>2</sup>/16-n-1</em>.







</FONT>

</BODY>

</HTML>

